#define _CRT_SECURE_NO_WARNINGS

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 // int Find_Left(int *arr, int arrSize, int x)
 // {
 //     int left = 0;
 //     int right = arrSize - 1;
 //     int ret = 0;

 //     while (left <= right)
 //     {
 //         int mid = (right - left) / 2 + left;

 //         if (arr[mid] > x)
 //             right = mid - 1;
 //         else
 //         {
 //             ret = mid;
 //             left = mid + 1;
 //         }
 //     }

 //     return ret;
 // }

int Find_Right(int* arr, int arrSize, int x)
{
    int left = 0;
    int right = arrSize - 1;

    while (left < right)
    {
        int mid = (right - left) / 2 + left;

        if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid;
    }

    return left;
}

int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
    *returnSize = k;
    int* ret = (int*)malloc(sizeof(int) * k);

    int right = Find_Right(arr, arrSize, x);
    int left = right - 1;

    for (int i = 0; i < k; i++)
    {
        if (right >= arrSize || left >= 0 && abs(arr[left] - x) <= abs(arr[right] - x))
            left--;
        else
            right++;


    }

    int index = 0;
    for (int i = left + 1; i < right; i++)
        ret[index++] = arr[i];

    return ret;
}